import java.util.*;


public class Solution5 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        int[][] dp = new int[str1.length()][str2.length()];
        boolean flgi = true;
        boolean flgj = true;
        for(int i = 0;i<str1.length();i++) {
            for(int j = 0;j<str2.length();j++) {
                if(i == j && i == 0) {
                    if(str1.charAt(i) == str2.charAt(j)) {
                        dp[i][j] = 0;
                        flgi = false;
                        flgj = false;
                    } else {
                        dp[i][j] = 1;
                    }
                } else if(i == 0) {
                    if(flgi && str1.charAt(i) == str2.charAt(j)) {
                        dp[i][j] = dp[i][j-1];
                        flgi = false;
                    } else {
                        dp[i][j] = dp[i][j-1] + 1;
                    }
                    
                } else if(j == 0) {
                    if(flgj && str1.charAt(i) == str2.charAt(j)) {
                        dp[i][j] = dp[i-1][j];
                        flgj = false;
                    } else {
                        dp[i][j] = dp[i-1][j] + 1;
                    }
                } else {
                    if(str1.charAt(i) == str2.charAt(j)) {
                        dp[i][j] = dp[i-1][j-1];
                    } else {
                        dp[i][j] = Math.min(dp[i][j-1],Math.min(dp[i-1][j-1],dp[i-1][j])) + 1;
                    }
                }
            }
        }
        return dp[str1.length()-1][str2.length()-1];
    }
}